package MAIN;
//笔试强训第23天
/*选择题*/
/*问一颗完全二叉树第6层有9个叶子节点，此时节点数最多有多少个？  第6层有9个叶子节点，此时求
* 最大节点个数，就认为存在第7层，并且第6层的节点是满的，此时一直到第6层，总的叶子节点个数是
* 2^6 - 1 = 63,第六层本身节点个数 2^(6-1) = 32, 除去9个叶子节点其他的叶子节点都是度
* 为2的节点，所以第7层的节点个数就是 （32-23）*2 = 46，总的节点个数就是63 + 46 = 109*/
/*堆的插入和删除操作都是在末尾进行操作，堆是一颗完全二叉树，所以可以使用数组来存放堆中的元素，
* 插入操作：在末尾插入之后，然后进行向上调整*/
/*用线性探测法解决冲突，平均查找长度：查找次数/数组元素个数（数组最大下标）*/

import java.util.Arrays;
import java.util.Scanner;
//编程题
public class Main23 {
    //微信红包(找数组中相同的元素超过数组长度的一半的那个元素)
    //元素个数就是数组长度
    public int getValue(int[] gifts, int n) {//数组长度
        Arrays.sort(gifts);
        int mid = gifts[n / 2];
        int count = 0;//统计数组中间数据出现的次数
        for (int i = 0; i < gifts.length; i++) {
            if (mid == gifts[i]) count++;
        }
        if (count > n / 2) return mid;
        else return 0;
    }
    //计算字符串的距离
    //计算字符串的距离
    //可用的操作：插入，删除，替换     一次操作只能替换一个字符
    //编辑距离：最小操作次数
    /*动态规划：   子问题：字符串A的一部分转换成字符串B的一部分的编辑距离
     * 状态F(i，j)：字符串A的前i个字符转换成字符串B的前j个字符的编辑距离
     * 状态转移方程：F(i,j) = min{F(i,j-1)+1, F(i-1,j)+1, F(i-1,j-1)+(A[i] == B[j] ? 0 : 1}
     * 初始状态：F(0,j) = j(插入) 代表从一个空串变成j串
     * F(i,0) = i(删除) 代表从一个i串变成空串  */
    public static int getDistance(String str1,String str2) {
        char[] wd1 = str1.toCharArray();
        char[] wd2 = str2.toCharArray();
        int len1 = wd1.length;
        int len2 = wd2.length;
        //定义一个矩阵   下标是从0开始的
        int[][] dist = new int[len1 + 1][len2 + 1];
        //初始状态 F(i,0) = i;（） F(0,j) = j;
        for (int i = 0; i <= len1; i++) {
            dist[i][0] = i;
        }
        for (int j = 0; j <= len2; j++) {
            dist[0][j] = j;
        }
        for (int i = 1; i <= len1; i++) {
            for (int j = 0; j <= len2; j++) {
                //首先求出插入和删除的最小值
                dist[i][j] = Math.min(dist[i-1][j],dist[i][j-1]) + 1;
                //再和替换进行比较
                if (wd1[i-1] == wd2[j-1]) {
                    //不需要进行替换
                    dist[i][j] = Math.min(dist[i][j], dist[i - 1][j - 1]);
                }else {
                    //需要进行替换
                    dist[i][j] = Math.min(dist[i][j],dist[i-1][j-1] + 1);
                }
            }
        }
        return dist[len1][len2];
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        while (scan.hasNextLine()) {
            String str1 = scan.nextLine();
            String str2 = scan.nextLine();
            System.out.println(getDistance(str1,str2));
        }
    }
}












